/**
* @description: 820. 单词的压缩编码
* @author hewei
* @date 2022/8/30 16:20
* @version 1.0
*/

public class MinimumLengthEncoding {

    public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        int ans = 0;
        for (int i = 0; i < words.length; i++) {
            words[i] = new StringBuilder(words[i]).reverse().toString();
            trie.add(words[i]);
        }
        for (String word : words) {
            if (!trie.search(word)) ans += word.length() + 1;
        }
        return ans;
    }

    static class Trie {
        Trie[] next;
        int end;
        int count;

        public Trie() {
            next = new Trie[26];
            end = 0;
            count = 0;
        }

        public void add(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                int index = c - 'a';
                if (node.next[index] == null) node.next[index] = new Trie();
                node.next[index].count++;
                node = node.next[index];
            }
            node.end++;
        }

        public boolean search(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) node = node.next[s.charAt(i) - 'a'];
            if (node.count != 1) {
                node.count--;
                return true;
            }
            return false;
        }
    }
}
